#include <stdio.h>

//每次找到一个最大的元素与末尾的交换
int findMaxEleIndex(int arr[], int n) {
	int index = 0;
	int max = arr[0];
	int i;

	for (i = 0; i < n; ++i) {
		if (arr[i] > max) {
			max = arr[i];
			index = i;
		}		
	}

	return index;
}

//交换函数
void swap(int* x, int* y) {
	int temp = *x;
	*x = *y;
	*y = temp;
}

//完成一次选择
void selection(int arr[], int n) {
	while (n > 1) {
		int pos = findMaxEleIndex(arr, n);
		swap(&arr[pos], &arr[n - 1]);
		--n;
	}
}

//递归选择排序
int selectionSort(int arr[], int n) {
	if (n == 1) {
		return 0;
	}
	else {
		selection(arr, n);
		selectionSort(arr, n - 1);
	}
}


//打印数组
void print(int arr[], int n) {
	int i;
	for (i = 0; i < n; ++i) {
		printf("%d ", arr[i]);
	}
	printf("\n");
}

int main() {
	int arr[5] = {2, 5, 7, 3, 1};
	printf("Before: ");
	print(arr, 5);

	selectionSort(arr, 5);

	printf("After: ");
	print(arr, 5);

	return 0;
}
